#include"sort.h"

const int N = 20010;
int temp[N];   //临时数组（用于归并排序）

void InsertSort(vector<int>& a)
{
	//插入排序核心思想：依次从第二个数顺序找到其应该插入的位置后进行插入---有序序列的插入
	for (int i = 1; i < a.size(); ++i)  //从第二个数开始找插入位置进行插入
	{
		int j;
		int CurData = a[i];    //后移过程中可能会占掉a[i]的当前元素，故需要暂存防止丢失当前元素值
		for (j = i-1; j >= 0; --j)  //反向寻找，不满足升序关系则使元素后移，最终给该数空出来一个其应在的位置
		{
			if (a[j] > CurData)   //如果当前元素大于待插入元素，则使当前元素后移（覆盖）
			{
				a[j + 1] = a[j];
			}
			else break;  //如果出现了第一个满足升序的位置（当前元素小于等于待插入元素）即为插入位置的上一个位置，break即可
		}
		a[j+1] = CurData;  //找到正确的插入位置后进行插入
	}
}

void BubbleSort(vector<int>& a)
{
	//冒泡排序核心思想：共排n-1趟，每趟俩相邻元素依次比较，若不符合升序则交换，最终每趟结果将剩余的最大的交换放置最后
	for (int i = 0; i < a.size() - 1; ++i)
	{
		bool flag = false;
		for (int j = 0; j < a.size()-i-1; ++j)  //由于每趟会排好一个数将其交换放置最后，故每趟交换的个数会从n-1依次减小
		{
			if(a[j]>a[j+1])  //如果前大后小
			{
				flag = true;
				swap(a[j], a[j + 1]);
			}
		}
		if (!flag) return;  //如果一趟下来没有发生一次交换则证明数据已有序
	}
}

void SelectSort(vector<int>& a)
{
	//选择排序核心思想：每次从序列挑出来剩余的最小的，将其与最前面的元素依次交换
	for (int i = 0; i < a.size(); ++i)
	{
		int min_i = i;   
		for (int j = i + 1; j < a.size(); ++j)
		{
			if (a[min_i] > a[j])
				min_i = j;
		}
		if (min_i != i)
			//注意这里的交换是对数组中的俩个元素，万万不可直接遍历一遍数组得到最小元素的值而不是最小元素的下标，
			//这样让最小元素的值与当前的元素进行交换，只是会让当前元素变为最小元素的值，并没有起到数组中俩个元素交换的作用
			swap(a[i], a[min_i]);  
	}
}

int partition(vector<int>& a, int l, int r)
{
	//先把比pivot小的放到前面，再把比pivot大的放到后面
	int pivot = a[l], i = l, j = r;
	while (i < j)  //因为头指针i记录着pivot，故要先从尾指针找起--->循环内的俩个循环顺序不可颠倒
	{
		while (a[j] >= pivot && i < j) --j;   //如果尾指针j所指的元素均大于等于pivot，则一直移动尾指针
		a[i] = a[j];   //若此时i<j且出现尾指针j所指元素值小于pivot，则将现在尾指针所指向的元素值覆盖头指针所指向的元素值
		while (a[i] <= pivot && i < j) ++i;   //如果头指针i所指的元素均小于等于pivot，则一直移动头指针
		a[j] = a[i];  //若此时i<j且出现头指针i所指元素值大于pivot，则将现在头指针所指向的元素值覆盖尾指针所指向的元素值
	}
	a[i] = pivot;   //因为循环出来后，i会等于j,故将pivot放至正确位置i/j
	return i;   //返回i/j
}

void QuickSort(vector<int>& a, int l, int r)
{
	if (l >= r) return;
	else  //l<r
	{
		int mid = partition(a, l, r);
		QuickSort(a, l, mid), QuickSort(a, mid + 1, r);
	}
}

void MergeSort(vector<int>& a, int l, int r)   
{
	//自顶向下
	if (l >= r) return;   //区间内只剩1个或0个元素时不用再进行归并排序
	int mid = l + r >> 1;
	MergeSort(a, l, mid), MergeSort(a, mid + 1, r);

	int i = l, j = mid+1,k=0;
	while (i <= mid && j <= r)   //每次挑出最小的
	{
		if (a[i] <= a[j]) temp[k++] = a[i++];
		else temp[k++] = a[j++];
	}

	//将俩个剩下的左/右子区间元素全部放至temp即可
	while (i <= mid) temp[k++] = a[i++];
	while (j <= r) temp[k++] = a[j++];

	//最终拷回原数组a[]
	for (int i = l, j = 0; i <= r; ++i,++j) a[i] = temp[j];
}